/*
 * @Author: liusheng
 * @Date: 2022-06-07 16:26:48
 * @LastEditors: liusheng
 * @LastEditTime: 2022-06-08 20:38:38
 * @Description: 剑指 Offer II 076. 数组中的第 k 大的数字
 * email:liusheng613@126.com
 * Copyright (c) 2022 by liusheng/liusheng, All Rights Reserved. 
 * 
 剑指 Offer II 076. 数组中的第 k 大的数字
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

 

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
 

提示：

1 <= k <= nums.length <= 104
-104 <= nums[i] <= 104
 

注意：本题与主站 215 题相同： https://leetcode-cn.com/problems/kth-largest-element-in-an-array/

通过次数22,081   提交次数32,488
 */

#include "header.h"

/*using std::priority_queue solution*/
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int,vector<int>,greater<int>> littleEidianpq;
        for (auto num: nums)
        {
            if (littleEidianpq.size() < k)
            {
                littleEidianpq.emplace(num);
            }
            else
            {
                if (num > littleEidianpq.top())
                {
                    littleEidianpq.pop();
                    littleEidianpq.emplace(num);
                }
            }
        }
        
        return littleEidianpq.top();
    }
};

/*
using quicksort
partition possible implementation:

template<class ForwardIt, class UnaryPredicate>
ForwardIt partition(ForwardIt first, ForwardIt last, UnaryPredicate p)
{
    first = std::find_if_not(first, last, p);
    if (first == last) return first;
 
    for (ForwardIt i = std::next(first); i != last; ++i) {
        if (p(*i)) {
            std::iter_swap(i, first);
            ++first;
        }
    }
    return first;
}
*/
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        quickSort(nums,0,nums.size()-1);
        return nums[nums.size() - k];
    }
private:
    void quickSort(vector<int> & nums,int low,int high)
    {
        if (low < high)
        {
            int pivot = partition(nums,low,high);
            quickSort(nums,low,pivot-1);
            quickSort(nums,pivot + 1,high);
        }
    }

    int partition(vector<int> & nums,int low,int high)
    {
        int pivotVal = nums[low];
        while (low < high)
        {
            while (low < high && nums[high] >= pivotVal) --high;
            nums[low] = nums[high];
            while (low < high && nums[low] <= pivotVal) ++low;
            nums[high] = nums[low];
        }
        
        nums[low] = pivotVal;

        return low;
    }
};

/*
improve above solution:just use partition,no need to sort all array
*/
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int low = 0;
        int high = nums.size() - 1;
        int pivot = 0;
        while (low < high)
        {
            pivot = partition(nums,low,high);
            if (pivot == nums.size() - k)
            {
                break;
            }
            else if (pivot < nums.size() - k)
            {
                low = ++pivot;
            }
            else
            {
                high = --pivot;
            }
        }

        // printf("after pivot:\n");
        // for (int i = 0; i <= pivot; ++i)
        // {
        //     printf("%d ",nums[i]);
        // }
        // printf("\n");
        return nums[pivot];
    }
private:
    // void quickSort(vector<int> & nums,int low,int high)
    // {
    //     if (low < high)
    //     {
    //         int pivot = partition(nums,low,high);
    //         quickSort(nums,low,pivot-1);
    //         quickSort(nums,pivot + 1,high);
    //     }
    // }

    int partition(vector<int> & nums,int low,int high)
    {
        int pivot = high;
        int pivotVal = nums[high];
        // printf("pivot:%d,pivotVal:%d\n",pivot,pivotVal);
        while (low < high)
        {
            while (low < high && nums[low] <= pivotVal) ++low;
            nums[high] = nums[low];
            
            while (low < high && nums[high] > pivotVal) --high;
            nums[low] = nums[high];
        }
        
        nums[low] = pivotVal;
        // printf("pivot:%d,pivotVal:%d\n",pivot,pivotVal);
        return low;
    }
};

/*
use heap select:build maxheap->maxheapfy
*/
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        buildMaxHeap(nums);
        int length = nums.size();
        int heapSize = length;

        for (int i = length - 1; i > length - k; --i )
        {
            swap(nums[i],nums[0]);
            --heapSize;
            maxHeapfy(nums,0,heapSize);
        }

        // printf("after maxHeapfy:\n");
        // for (int i = 0; i < length; ++i)
        // {
        //     printf("%d ",nums[i]);
        // }
        // printf("\n");
        return nums[0];
    }
private:
    void maxHeapfy(vector<int> & nums,int i,int heapSize)
    {
        int leftChild = 2 * i + 1;
        int rightChild = 2 * i + 2;
        int largest = i;

        if (leftChild < heapSize && nums[leftChild] > nums[largest])
        {
            largest = leftChild;
        }

        if (rightChild < heapSize && nums[rightChild] > nums[largest])
        {
            largest = rightChild;
        }

        if (largest != i)
        {
            swap(nums[i],nums[largest]);
            //this largest position store the previous i
            //position value
            maxHeapfy(nums,largest,heapSize);
        }
    }

    void buildMaxHeap(vector<int> & nums)
    {
        int length = nums.size();
        for (int i = nums.size() / 2; i >= 0; i--)
        {
            maxHeapfy(nums,i,length);
        }
    }
};